(module static-data-structures (lib "eopl.ss" "eopl")

  (require "lang.scm")                  ; for expression?, type?, etc.

  (provide (all-defined))               ; too many things to list

  (define-datatype type-environment type-environment?
    (empty-tenv)
    (extend-tenv 
      (bvar symbol?)
      (bval type?)
      (saved-tenv type-environment?))
    (extend-tenv-with-module
      (m-name symbol?)
      (m-type module-type?)
      (saved-tenv type-environment?))
    (extend-tenv-with-abstype
      (t-name symbol?)
      (saved-tenv type-environment?))
    (extend-tenv-with-type-abbrev
      (t-name symbol?)
      (t-type type?)
      (saved-tenv type-environment?))
    )

  ;;;;;;;;;;;;;;;; procedures for looking things up tenvs ;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;; lookup or die

  (define lookup-module-name-in-tenv
    (lambda (tenv search-sym)
      (let ((maybe-answer
              (module-name->maybe-binding-in-tenv tenv search-sym)))
        (if maybe-answer maybe-answer
          (eopl:error 'lookup-module-name-in-tenv
            "Unbound module name ~s in tenv ~s"
            search-sym tenv)))))

  (define lookup-variable-name-in-tenv
    (lambda (tenv search-sym)
      (let ((maybe-answer
              (variable-name->maybe-binding-in-tenv tenv search-sym)))
        (if maybe-answer maybe-answer
          (eopl:error 'lookup-variable-name-in-tenv
            "Unbound variable name ~s in tenv ~s"
            search-sym tenv)))))

  ;;;;;;;;;;;;;;;; lookup or return #f.

  (define variable-name->maybe-binding-in-tenv
    (lambda (tenv search-sym)
      (let recur ((tenv tenv)) 
         (cases type-environment tenv
          (empty-tenv () #f)
          (extend-tenv (name ty saved-tenv)
            (if (eqv? name search-sym) 
              ty
              (recur saved-tenv)))
          (else (recur (tenv->saved-tenv tenv)))))))

  (define module-name->maybe-binding-in-tenv
    (lambda (tenv search-sym)
      (let recur ((tenv tenv)) 
         (cases type-environment tenv
          (empty-tenv () #f)
          (extend-tenv-with-module (name m-type saved-tenv)
            (if (eqv? name search-sym) 
              m-type
              (recur saved-tenv)))
          (else (recur (tenv->saved-tenv tenv)))))))

  ;; take a declaration, translate it to a binding, and add it to the tenv.

  (define extend-tenv-with-declaration
    (lambda (decl tenv)
      (cases declaration decl
        (type-abbrev-declaration (name ty)
          (extend-tenv-with-type-abbrev name ty tenv))
        (val-declaration (name ty) 
          (extend-tenv name ty tenv))
        (abstract-type-declaration (name)
          (extend-tenv-with-abstype name tenv)))))

  ;; assumes tenv is non-empty.  
  (define tenv->saved-tenv
    (lambda (tenv)
      (cases type-environment tenv
        (empty-tenv () 
          (eopl:error 'tenv->saved-tenv
            "tenv->saved-tenv called on empty tenv"))
        (extend-tenv (name ty saved-tenv) saved-tenv)
        (extend-tenv-with-module (name m-type saved-tenv) saved-tenv)
        (extend-tenv-with-abstype (name saved-tenv) saved-tenv)
        (extend-tenv-with-type-abbrev (name ty saved-tenv) saved-tenv)
        ;; (extend-tenv-with-interface (name m-type saved-tenv) saved-tenv)
        )))

  ;; find first element of lst for which predicate returns non-#f, and
  ;; return that value.
  (define linsearch
    (lambda (lst val-for-null predicate)
      (cond
        ((null? lst) val-for-null)
        ((predicate (car lst)) => (lambda (b) b))
        (else (linsearch (cdr lst) val-for-null predicate)))))

  ;; or get the rightmost one
  (define linsearchr
    (lambda (lst val-for-null predicate)
      (linsearch (reverse lst) val-for-null predicate)))

  
  )
                    